﻿//【初阶】29.二叉树+map+set
//【头文件包含】
//C++的主要头文件
#include<iostream>//c++的输入输出流
using namespace std;
#include<string>
//using std::cout, std::endl, std::cin;
#include<vector>
#include<list>
#include<set>
#include<map>
//C的主要头文件
//#include<stdio.h>
//#include<stdlib.h>
//#include<assert.h>
//#include<string.h> 



//【命名空间】

//【结构体声明】【类声明】
////K/V的键值对
//template <class T1, class T2>
//struct pair
//{
//	typedef T1 first_type;
//	typedef T2 second_type;
//	T1 first;
//	T2 second;
//	pair() : first(T1()), second(T2())
//	{
//	}
//	pair(const T1& a, const T2& b) : first(a), second(b)
//	{
//	}
//};


//【函数声明】
void Test1();void Test2();void Test3();void Test4();


//【主函数】
int main()
{
	Test1();
	Test2();
	Test3();
	Test4();
	
	cout << "****主函数结束****" << endl;
	return 0;
}

//【函数定义】


/*测试用例*/void Test1()
{
	cout << "****测试用例开始****"<< endl;
	set<int> s;
	s.insert(3);
	s.insert(1);
	s.insert(4);
	s.insert(3);
	s.insert(7);
	cout << s.size() << endl;

	cout <<s.erase(3)<< endl;
	std::set<int>::iterator ret1 = s.find(1);
	std::set<int>::iterator ret2= find(s.begin(), s.end(), 4);
	s.erase(ret1);
	s.erase(ret2);
	for (auto& a : s)
	{
		cout << a << " ";
	}
	cout << endl;

	cout << "****测试用例结束****" << endl << endl;
}

/*测试用例*/void Test2()
{
	cout << "****测试用例开始****" << endl;
	int array[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };
	set<int> s(array, array + sizeof(array) / sizeof(array[0]));

	cout << s.size() << endl;

	// 正向打印set中的元素，从打印结果中可以看出：set可去重
	for (auto& e : s)
		cout << e << " ";
	cout << endl;

	// 使用迭代器逆向打印set中的元素
	for (auto it = s.rbegin(); it != s.rend(); ++it)
		cout << *it << " ";
	cout << endl;

	// set中值为3的元素出现了几次
	cout << s.count(3) << endl;
	cout << "****测试用例结束****" << endl<<endl;
}

/*测试用例*/void Test3()
{
	cout << "****测试用例开始****" << endl;
	map<int,int> m;
	m.insert(pair<int, int>(1, 1));
	m.insert(pair<int, int>(3, 4));
	m.insert(pair<int, int>(2, 2));
	m.insert(pair<int, int>(4, 2));
	m.insert(pair<int, int>(5, 1));
	m.insert(make_pair(6, 1));
	//m.insert(3, 1);
	for (auto& a : m)
	{
		cout << a.first << ":" << a.second << "  ";
	}
	cout << endl;

	cout << "****测试用例结束****" << endl << endl;
}

/*测试用例*/void Test4()
{
	cout << "****测试用例开始****" << endl;
	std::string strs[] = { "find","cur","std","map","set","set","map","string","map","cur" };
	std::map<std::string, int> countmap;
	for (auto& a : strs)
	{
		std::map<std::string, int>::iterator ret = countmap.find(a);
		if (ret != countmap.end())
		{
			ret->second++;
		}
		else
		{
			countmap.insert(make_pair(a, 1));
		}
	}
	for (auto& a : countmap)
	{
		cout << a.first << ":" << a.second << endl;
	}
	cout << endl;

	cout << "****测试用例结束****" << endl << endl;
}

//【笔记】
//【初阶】29.二叉树+map+set
//map和set
	// 关联式容器
		//set/map/unordered_map/unordered_set
	// 序列式容器
		//vector/list/string/deque
	//set 是K的模型 map是K/V的模型
	//【set】底层为搜索树
		// 支持迭代器、范围for、插入、删除。。。
		//	erase:
			// 支持迭代器删除，没有返回值
			// 支持元素值删除返回删除元素个数
			// 还支持删除一个迭代器范围内的值，没有返回值
		// find：区别于通用的find，内置的find效率更高
	//【map】
		//K/V的键值对pair //用来表示具有一一对应关系的一种结构，
			//该结构中一般只包含两个成员变量key和value，key代表键值value表示与key对应的信息
			//在map插入元素时是以键值对的对象进行插入,insert等传递的参数为 value_type对应-》pair<const key_type,maped_type>
			// 可以使用pair<const key_type,maped_type>(key,value)g调用构造||还可使用make_pair（key,value）调用模版参数
			// c++17以上支持pair（key，value），会自动推导格式，无需制定，但在低版本要注意明确出参数类型
			// 一般情况下make_pair更便捷
		//map的使用和set类似
	//set虽然使用时只传入key即可但其底层仍是由键值对构成，只不过使用的是<key,key>的，底层实现原理是二叉搜索树（红黑树）
	//map是完全的关联容器，使用key来搜索排序，每个元素key值唯一不可被修改





